﻿\subsection{Дробные абелевы степени}
\label{subsection:abelian-intro}

Впервые \textit{абелевы степени} были предложены Эрдёшем \cite{Erdos} в качестве естественного обобщения
<<обычных>> степеней. Слово $w_1w_2\ldots w_n$ называется \textit{абелевой $n$-й степенью}, если все слова
$w_2,\ldots,w_n$ являются анаграммами $w_1$. Это условие эквивалентно тому, что $w_1=w_2=\ldots=w_n$
в любой коммутативной полугруппе, или тому, что частотные векторы слов $w_1,\ldots,w_n$ совпадают.
В отличие от обычных степеней, существует несколько способов обобщить понятие абелевой степени на
дробные экспоненты. Ниже мы определяем слабые, полустрогие и строгие дробные абелевы степени и работаем
со всеми тремя определениями.

Избегаемость целых абелевых степеней хорошо изучена. Легко проверить, что абелевы квадраты
3-неизбежны, а абелевы кубы 2-неизбежны. С другой стороны, язык абелево бесквадратных слов
над алфавитом размера 4 бесконечен \cite{Keranen} и растёт экспоненциально \cite{Carpi-1}.
Это справедливо также для языка абелево бескубных слов над тернарным алфавитом и языка абелево
4-свободных слов над бинарным алфавитом (бесконечность доказана в \cite{Dekking}, а экспоненциальный рост~---
в \cite{ACR,Currie}). Однако, полученные оценки индексов роста этих языков далеки от реальных
значений (например, Карпи оценил снизу количество абелево бесквадратных слов длины $n$ над алфавитом
размера 4 как $\Omega(1{,}000021^n)$), поэтому поиск более точных оценок индексов роста
этих языков представляет интерес. Некоторые такие оценки приведены в данной работе.

Если мы выберем одно из определений дробных абелевых степеней, \textit{абелеву границу повторяемости} можно
определить так же, как и <<обычную>> границу повторяемости. Мы изучаем значения абелевой границы повторяемости
для всех алфавитов и для трёх различных определений дробных абелевых степеней.

Рассмотрим целое $m \ge 2$. \textit{абелева $m$-я степень}~--- это слово вида $w_{1}w_{2} \ldots w_{m}$,
где $w_{i}$ является анаграммой $w_{1}$ для $2 \le i \le m$, или, \hbox{$\vec p(w_1)=\ldots=\vec p(w_m)$}.
Обобщим это определение на вещественные числа из промежутка
$(1,\infty)$. Пусть $\beta > 1$,  $|w_1|=q$, $m=\lfloor\beta\rfloor$, $t=\lceil\{\beta\}q\rceil$,
где $\{\beta\}$ означает дробную часть $\beta$. Рассмотрим слово вида $w = w_{1} \ldots w_{m}v$,
где $w_{1} \ldots w_{m}$ является абелевой $m$-степенью, и $|v| = t$.
В данной работе термины \textit{корень} и \textit{хвост} по отношению к абелевым степеням
означают слова $w_{1}$ и $v$ соответственно. Чтобы слово $m$ можно было считать абелевой $\beta$-степенью,
требуется наложить дополнительное ограничение на частотный вектор хвоста. Мы рассматриваем три
таких ограничения, таким образом получая три определения дробной абелевой степени. Пусть $\mathrm{pref}(u, l)$
означает префикс $u$ длины $l$.

\textit{Слабая абелева $\beta$-степень}~--- это слово $w$ описанного выше вида, в котором $\vec p(v)\le\vec p(w_1)$.
То есть, хвост является префиксом анаграммы корня.

\textit{Строгая абелева $\beta$-степень}~--- это слово $w$ описанного выше вида, в котором
$\vec p(v)=\vec p(\mathrm{pref}(w_1,t))$. То есть, хвост является анаграммой префикса корня.
Однако, в этом определении мы явно выделяем корень среди всех слов $w_{i}$, поскольку
хвост не зависит от порядка букв в $w_{i}$ для $2 \le i \le m$. Если поменять местами
$w_{1}$ и $w_{2}$, слово может стать (или перестать быть) строгой абелевой степенью.
Например, слово $abc\,cab\,ba$ является строгой абелевой $8/3$-степенью, а слово $cab\,abc\,ba$~--- нет.
Чтобы избавиться от этого, мы вводим следующее определение:

\textit{Полустрогая абелева $\beta$-степень}~--- это слово $w$ описанного выше вида, в котором
$\vec p(v)\le\!\!\bigvee\limits_{i=\overline{1,m}}\!\!\vec p(\mathrm{pref}(w_i,t))$, где $\bigvee$~---
это операция взятия максимума покомпонентно.
Таким образом, все $w_i$ симметрично используются в ограничении, накладываемом на хвост,
как в определении слабой абелевой степени.

\begin{rmrk} \label{abel1}
(1) Для целых $\beta$ все три определения эквивалентны определению целой абелевой степени.\\
(2) Для $\beta \le 2$ определения строгой и полустрогой абелевых $\beta$-степеней эквивалентны.\\
(3) Любая строгая абелева $\beta$-степень также является полустрогой абелевой $\beta$-степенью, любая полустрогая
$\beta$-степень также является слабой абелевой $\beta$-степенью.
\end{rmrk}

\begin{xmpl}
Слово $abc\,cba\,ac$ является полустрогой абелевой $(8/3)$-степенью и слабой абелевой $(8/3)$-степенью, но не
строгой абелевой $(8/3)$-степенью, поскольку $ac$ не является перестановкой $ab$. Слово $abcaa$ не является даже слабой абелевой $(5/3)$-степенью,
но является строгой, полустрогой и слабой абелевой $(5/4)$-степенью.
\end{xmpl}

\begin{rmrk} \label{abel2}
Существует несколько способов сделать определение строгой абелевой $\beta$-степени <<симметричным>>.
Приведённое определение полустрогой абелевой $\beta$-степени использует наиболее слабые ограничения на
частотный вектор хвоста. В параграфе \ref{subsection:abelian-results} мы увидим, что предполагаемое значение
абелевой границы повторяемости совпадает для строгих и полустрогих степеней. Поэтому, с точки зрения
абелевой границы повторяемости, изучение других <<симметризаций>> не имеет смысла.
\end{rmrk}

\textit{Абелева экспонента} слова $w \in \Sigma^{*}$~--- это такое максимальное вещественное число $\beta$,
что $w$ является абелевой $\beta$-степенью. \textit{Абелево $\beta$-свободный (абелево $\beta^{+}$-свободный) язык} состоит
из всех слов, абелева экспонента которых меньше $\beta$ (не больше $\beta$).
Мы рассматриваем три типа абелево $\beta$-свободных языков в зависимости от выбранного определения дробной
абелевой степени (строгая, полустрогая или слабая). Чтобы сравнить эти определения, разумно сравнить размеры
соответствующих языков. Поскольку абелево $\beta$-свободные языки являются факториальными, мы можем оценивать их
индексы роста с помощью метода, описанного в разделе \ref{section:theory}.
В параграфе \ref{subsection:abelian-algo} рассмотрен алгоритм построения антисловарей таких языков.
